package Leetcode.Dichotomy;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/4/5 15:20
 * @Description:
 *
 * 爱吃香蕉的珂珂
 *
 * 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
 *
 * 珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
 *
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 *
 * 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
 *
 * 示例 1：
 *
 * 输入：piles = [3,6,7,11], h = 8
 * 输出：4
 * 示例 2：
 *
 * 输入：piles = [30,11,23,4,20], h = 5
 * 输出：30
 * 示例 3：
 *
 * 输入：piles = [30,11,23,4,20], h = 6
 * 输出：23
 *
 *
 * 提示：
 *
 * 1 <= piles.length <= 104
 * piles.length <= h <= 109
 * 1 <= piles[i] <= 109
 */

public class minEatingSpeed {
    public static void main(String[] args) {
        int[] piles = {3, 6, 7, 11};
        int h = 8;
/*        int numerator = 6;
        int denominator = 2;

        double result1 = Math.ceil((double) numerator / denominator); // 向上取整
        System.out.println("6/2 的向上取整结果是： " + result1); // 输出 6/2 的向上取整结果是： 3.0

        int numerator2 = 6;
        int denominator2 = 4;

        double result2 = Math.ceil((double) numerator2 / denominator2); // 向上取整
        System.out.println("6/4 的向上取整结果是： " + result2); // 输出 6/4 的向上取整结果是： 2.0*/
        System.out.println(minEatingSpeed2(piles, h));
    }

    /**
     *
     * @param piles
     * @param h
     * @return
     */
    public static int minEatingSpeed1(int[] piles, int h) {
        int left = 0, right = Arrays.stream(piles).max().getAsInt();
        while (left+1 < right) {
            int mid = left + (right - left) / 2;
            if (check(mid,piles, h)) {
                right = mid ;
            }else{
                left = mid;
            }
        }
        return right;
    }

    public static int minEatingSpeed2(int[] piles, int h) {
        int left = 1, right = Arrays.stream(piles).max().getAsInt();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid,piles, h)) {
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 当前速度是否满足  不满足则应该加快速度  left+ 否则right-
     * @param mid
     * @param piles
     * @param h
     * @return
     */
    private static boolean check(int mid, int[] piles, int h) {
        int sum = piles.length;
        for (int pile : piles) {
            sum += (pile - 1) / mid;
            if (sum > h) {
                return false;
            }
        }
        return true;
    }

}
